The file of this patent application includes a computer program listing appendix stored on two identical read-only Compact Discs. Each Compact Disc has the computer program listing appendix stored as a file named xe2x80x9cappendix1.docxe2x80x9d that was created on Jul. 23, 2003 and is 249,856 bytes in size. This computer program listing appendix is hereby incorporated herein by reference.
The present invention relates to the creation of computer-generated images both in the form of still pictures and video imagery, and, in particular, relates to efficient process, apparatus, and system for creating an image made up by compositing multiple components.
Computer generated images are typically made up of many differing components or graphical elements which are rendered and composited together to create a final image. In recent times, an xe2x80x9copacity channelxe2x80x9d (also known as a xe2x80x9cmattexe2x80x9d, an xe2x80x9calpha channelxe2x80x9d, or simply xe2x80x9copacityxe2x80x9d) has been commonly used. The opacity channel contains information regarding the transparent nature of each element. The opacity channel is stored alongside each instance of a colour, so that, for example, a pixel-based image with opacity stores an opacity value as part of the representation of each pixel. An element without explicit opacity channel information is typically understood to be fully opaque within some defined bounds of the element, and assumed to be completely transparent outside those bounds.
An expression tree offers a systematic means for representating an image in terms of its constituent elements and which facilitates later rendering. Expression trees typically comprise a plurality of nodes including leaf nodes, unary nodes and binary nodes. Nodes of higher degree, or of alternative definition may also be used. A leaf node, being the outer most node of an expression tree, has no descendent nodes and represents a primitive constituent of an image. Unary nodes represent an operation which modifies the pixel data coming out of the part of the tree below the unary operator. Unary nodes include such operations as colour conversions, convolutions (blurring etc) and operations such as red-eye removal. A binary node typically branches to left and right subtrees, wherein each subtree is itself an expression tree comprising at least one leaf node. Binary nodes represent an operation which combines the pixel data of its two children to form a single result. For example, a binary node may be one of the standard xe2x80x9ccompositing operatorsxe2x80x9d such as OVER, IN, OUT, ATOP and alpha-XOR, examples of which and other are seen in FIG. 20.
Several of the above types of nodes may be combined to form a compositing tree. An example of this is shown in FIG. 1. The result of the left-hand side of the compositing tree may be interpreted as a colour converted image being clipped to spline boundaries. This construct is composited with a second image.
Although the non-transparent area of a graphical element may of itself be of a certain size, it need not be entirely visible in a final image, or only a portion of the element may have an effect on the final image. For example, assume an image of a certain size is to be displayed on a display. If the image is positioned so that only the top left corner of the image is displayed by the display device, the remainder of the image is not displayed. The final image as displayed on the display device thus comprises the visible portion of the image, and the invisible portion in such a case need not be rendered.
Another way in which only a portion of an element may have an effect is when the portion is obscured by another element. For example, a final image to be displayed (or rendered) may comprise one or more opaque graphical elements, some of which obscure other graphical elements. Hence, the obscured elements have no effect on the final image.
A conventional compositing model considers each node to be conceptually infinite in extent. Therefore, to construct the final image, a conventional system would apply a compositing equation at every pixel of the output image. Interactive frame rates of the order greater than 15 frames per second can be achieved by relatively brute-force approaches in most current systems, because the actual pixel operations are quite simple and can be highly optimised. This highly optimised code is fast enough to produce acceptable frame rates without requiring complex code. However, this is certainly not true in a compositing environment.
The per-pixel cost of compositing is quite high. This is because typically an image is rendered in 24-bit colour in addition to an 8-bit alpha channel, thus giving 32 bits per pixel. Each compositing operator has to deal with each of the four channels. Therefore, the approach of completely generating every pixel of every required frame when needed is inefficient, because the per-pixel cost is too high.
Problems arise with prior art methods when rendering graphical objects which include transparent and partially-transparent areas. Further, such methods typically do not handle the full range of compositing operators.
It is an object of the present invention to substantially overcome, or ameliorate, one or more of the deficiencies of the above mentioned methods by the provision of a method for creating an image made up by compositing multiple components.
According to one aspect of the present invention there is provided a method of creating an image, said image being formed by rendering at least a plurality of graphical objects to be composited according to a compositing expression, each said object having a predetermined outline, said method comprising the steps of:
dividing a space in which said outlines are defined into a plurality of mutually exclusive regions wherein each of said regions is defined by a region outline substantially following at least one of said predetermined outlines or parts thereof;
examining each said region to determine those said objects which contribute to said region;
modifying said compositing expression on the basis of the contribution of each of said objects within said region to form an optimized compositing expression for each said region; and
compositing said image using each of said optimized compositing expressions.
According to another aspect of the present invention there is provided a method of creating an image, said image being formed by rendering at least a plurality of graphical objects to be composited according to a compositing expression, each said object having a predetermined outline, said method comprising the steps of:
dividing a space in which said outlines are defined into a plurality of mutually exclusive regions;
examining each said region to determine those said objects which contribute to said region;
modifying said compositing expression on the basis of the contribution of each of said objects within said region; and
compositing said image using said modified compositing expression.
According to still another aspect of the present invention there is provided a method of creating an image, said image comprising a plurality of graphical objects to be composited according to a compositing expression, said method comprising the steps of:
dividing a space in which said graphical objects are defined into a plurality of regions;
examining each said region to determine those said objects which contribute to said region;
modifying said compositing expression on the basis of said examination; and
compositing said image using said modified compositing expression.
According to still another aspect of the present invention there is provided an apparatus for creating an image, said image being formed by rendering at least a plurality of graphical objects to be composited according to a compositing expression, each said object having a predetermined outline, said apparatus comprising:
dividing means for dividing a space in which said outlines are defined into a plurality of mutually exclusive regions wherein each of said regions is defined by a region outline substantially following at least one of said predetermined outlines or parts thereof;
examining means for examining each said region to determine those said objects which contribute to said region;
modifying means for modifying said compositing expression on the basis of the contribution of each of said objects within said region to form an optimized compositing expression for each said region; and
compositing means for compositing said image using each of said optimized compositing expressions.
According to still another aspect of the present invention there is provided an apparatus for creating an image, said image being formed by rendering at least a plurality of graphical objects to be composited according to a compositing expression, each said object having a predetermined outline, said apparatus comprising:
dividing means for dividing a space in which said outlines are defined into a plurality of mutually exclusive regions;
examining means for examining each said region to determine those said objects which contribute to said region;
modifying means for modifying said compositing expression on the basis of the contribution of each of said objects within said region; and
compositing means for compositing said image using said modified compositing expression.
According to still another aspect of the present invention there is provided an apparatus for creating an image, said image comprising a plurality of graphical objects to be composited according to a compositing expression, said apparatus comprising:
dividing means for dividing a space in which said graphical objects are defined into a plurality of regions;
examining means for examining each said region to determine those said objects which contribute to said region;
modifying means for modifying said compositing expression on the basis of said examination; and
compositing means for compositing said image using said modified compositing expression.
According to still another aspect of the present invention there is provided a method of creating a series of images, each member of said series being related to a preceding member, said images being formed by rendering a plurality of graphical objects to be composited according to a hierarchical structure representing a compositing expression, said hierarchical structure including a plurality of nodes each representing a component of at least one of said images, each of said objects having a predetermined outline, said method comprising the steps of:
(a) for each said node:
(i) dividing a component image space in which said outlines are defined into at least one mutually exclusive region, each said region being related to at least one graphical object;
(ii) examining each said region to determine those objects that contribute to the region;
(b) creating internodal dependency information identifying those said regions that will be affected by a change in any one of said regions;
(c) rendering a first image of said series by compositing all regions substantially according to said hierarchical structure;
(d) in response to at least one change to at least one of said nodes;
(i) examining said internodal dependency information to identify those of said regions affected by said at least one change;
(ii) for each node with affected regions, updating the corresponding identified regions and incorporating into said node those (any) new regions arising from the change and/or removing any of said regions that are no longer relevant;
(iii) updating said internodal dependency information to reflect changes to said hierarchical structure;
(iv) rendering a further image of said series by compositing (only) those regions affected by said at least one change; and
(e) repeating step (d) for further changes to at least one of said nodes.
According to still another aspect of the present invention there is provided a method of creating a series of images, said images being formed by rendering a plurality of graphical objects to be composited according to a hierarchical structure, said hierarchical structure including a plurality of nodes each representing a component of at least one of said images, each of said objects having a predetermined outline, said method comprising the steps of:
(a) for each said node:
(iii) dividing a space in which said outlines are defined into at least one mutually exclusive region;
(iv) examining each said region to determine those objects that contribute to the region;
(b) creating internodal dependency information based on said examination;
(c) rendering a first image of said series utilising said hierarchical structure; and then, in response to at least one change to at least one of said nodes;
(d) examining said internodal dependency information;
(i) for a node with affected regions, updating the corresponding regions;
(ii) updating said internodal dependency information;
(iii) rendering a further image of said series by compositing those regions affected by said at least one change; and
(e) repeating step (d) for further changes to at least one of said nodes.
According to still another aspect of the present invention there is provided a method of creating a series of images, said images being formed by rendering at least a plurality of graphical objects to be composited according to a hierarchical structure, said hierarchical structure including a plurality of nodes each representing a component of at least one of said images, said method comprising the steps of:
(a) for each said node:
(i) dividing a component image space in which said graphical objects are defined into at least one region;
(ii) examining each said region;
(b) creating internodal dependency information for each of said regions;
(c) rendering a first image of said series utilising said hierarchical structure; and then, in response to at least one change to at least one of said nodes;
(d) examining said internodal dependency information;
(i) for a node with affected regions, updating the corresponding information;
(ii) updating said internodal dependency record;
(iii) rendering a further image of said series; and
(e) repeating step (d) for further changes to at least one of said nodes.
According to still another aspect of the present invention there is provided an apparatus for creating a series of images, each member of said series being related to a preceding member, said images being formed by rendering a plurality of graphical objects to be composited according to a hierarchical structure representing a compositing expression, said hierarchical structure including a plurality of nodes each representing a component of at least of one of said images, each of said objects having a predetermined outline, said apparatus comprising:
dividing means for dividing a component image space in which said outlines are defined, for each said node, into at least one mutually exclusive region, each said region being related to at least one graphical object;
first examining means for examining each said region, for each said node, to determine those objects that contribute to the region;
creating means for creating an internodal dependency information identifying those said regions that will be affected by a change in any one of said regions;
rendering means for rendering a first image of said series by compositing all regions substantially according to said hierarchical structure;
second examining means for examining said internodal dependency information to identify those of said regions affected by at least one change to at least one of said nodes;
first updating means for updating the corresponding identified regions for each node with affected regions and incorporating into said node those (any) new regions arising from the change;
second updating means for updating said internodal dependency information to reflect changes to said hierarchical structure; and
rendering means for rendering a further image of said series by compositing (only) those regions affected by said at least one change.
According to still another aspect of the present invention there is provided an apparatus for creating a series of images, said images being formed by rendering at least a plurality of graphical objects to be composited according to a hierarchical structure, said hierarchical structure including a plurality of nodes each representing a component of at least one of said images, each of said objects having a predetermined outline, said apparatus comprising:
dividing means for dividing a space in which said outlines are defined, for each said node, into at least one mutually exclusive region;
first examining means for examining each said region, for each said node, to determine those objects that contribute to the region;
creating means for creating internodal dependency information based on said examination;
rendering means for rendering a first image of said series utilising said hierarchical structure; and
second examining means for examining said internodal dependency information in response to at least one change to at least one of said nodes and, for a node with affected regions, updating the corresponding regions, updating said internodal dependency information and, rendering a further image of said series by compositing those regions affected by said at least one change.
According to still another aspect of the present invention there is provided an apparatus for creating a series of images, said images being formed by rendering at least a plurality of graphical objects to be composited according to a hierarchical structure, said hierarchical structure including a plurality of nodes each representing a component of at least one of said images, said apparatus comprising:
dividing means for dividing a component image space, for each said node, in which said graphical objects are defined into at least one region;
first examining means for examining each said region;
creating means for creating internodal dependency information for each of said regions;
rendering means for rendering a first image of said series utilising said hierarchical structure;
second examining means for examining said internodal dependency information, in response to at least one change to at least one of said nodes; and
first updating means for updating the corresponding regions for an affected node;
second updating means for updating said internodal dependency information; and
rendering means for rendering a further image of said series.
According to still another aspect of the present invention there is provided a computer program product including a computer readable medium having a plurality of software modules for creating an image, said image being formed by rendering at least a plurality of graphical objects to be composited according to a compositing expression, each said object having a predetermined outline, said computer program product comprising:
dividing module for dividing a space in which said outlines are defined into a plurality of mutually exclusive regions wherein each of said regions is defined by a region outline substantially following at least one of said predetermined outlines or parts thereof;
examining module for examining each said region to determine those said objects which contribute to said region;
modifying module for modifying said compositing expression on the basis of the contribution of each of said objects within said region to form an optimized compositing expression for each said region; and
compositing module for compositing said image using each of said optimized compositing expressions.
According to still another aspect of the present invention there is provided a computer program product including a computer readable medium having a plurality of software modules for creating an image, said image being formed by rendering at least a plurality of graphical objects to be composited according to a compositing expression, each said object having a predetermined outline, said computer program product comprising:
dividing module for dividing a space in which said outlines are defined into a plurality of mutually exclusive regions;
examining module for examining each said region to determine those said objects which contribute to said region;
modifying module for modifying said compositing expression on the basis of the contribution of each of said objects within said region; and
compositing module for compositing said image using said modified compositing expression.
According to still another aspect of the present invention there is provided a computer program product including a computer readable medium having a plurality of software modules for creating an image, said image comprising a plurality of graphical objects to be composited according to a compositing expression, said computer program product comprising:
dividing module for dividing a space in which said graphical objects are defined into a plurality of regions;
examining module for examining each said region to determine those said objects which contribute to said region;
modifying module for modifying said compositing expression on the basis of said examination; and
compositing module for compositing said image using said modified compositing expression.
According to still another aspect of the present invention there is provided a computer program product including a computer readable medium having a plurality of software modules for creating a series of images, each member of said series being related to a preceding member, said images being formed by rendering a plurality of graphical objects to be composited according to a hierarchical structure representing a compositing expression, said hierarchical structure including a plurality of nodes each representing a component of at least one of said images, each of said objects having a predetermined outline, said computer program product comprising:
dividing module for dividing a component image space in which said outlines are defined, for each said node, into at least one mutually exclusive region, each said region being related to at least one graphical object;
first examining module for examining each said region, for each said node, to determine those objects that contribute to the region;
creating module for creating an internodal dependency information identifying those said regions that will be affected by a change in any one of said regions;
rendering module for rendering a first image of said series by compositing all regions of said hierarchical structure;
second examining module for examining said internodal dependency information to identify those of said regions affected by at least one change to at least one of said nodes;
first updating module for updating the corresponding identified regions for each node with affected regions and incorporating into said node those (any) new regions arising from the change;
second updating module for updating said internodal dependency information to reflect changes to said hierarchical structure; and
rendering module for rendering a further image of said series by compositing (only) those regions affected by said at least one change.
According to still another aspect of the present invention there is provided a computer program product including a computer readable medium having a plurality of software modules for creating a series of images, said images being formed by rendering a plurality of graphical objects to be composited according to a hierarchical structure, said hierarchical structure including a plurality of nodes each representing a component of at least one of said images, each of said objects having a predetermined outline, said computer program product comprising:
dividing module for dividing a space in which said outlines are defined, for each said node, into at least one mutually exclusive region;
first examining module for examining each said region, for each said node, to determine those objects that contribute to the region;
creating module for creating an internodal dependency information based on said examination;
rendering module for rendering a first image of said series utilising said hierarchical structure; and
second examining module for examining said internodal dependency information in response to at least one change to at least one of said nodes and, for a node with affected regions, updating the corresponding regions, updating said internodal dependency information and, rendering a further image of said series by compositing those regions affected by said at least one change.
According to still another aspect of the present invention there is provided a computer program product including a computer readable medium having a plurality of software modules for creating a series of images, said images being formed by rendering a plurality of graphical objects to be composited according to a hierarchical structure, said hierarchical structure including a plurality of nodes each representing a component of said image, said computer program product comprising:
dividing module for dividing a component image space, for each said node, in which said graphical objects are defined into at least one region;
first examining module for examining each said region;
creating module for creating internodal dependency information for each of said regions;
rendering module for rendering a first image of said series utilising said hierarchical structure;
second examining module for examining said internodal dependency information, in response to at least one change to at least one of said nodes; and
first updating module for updating the corresponding regions for a node with affected regions;
second updating module for updating said internodal dependency information; and
rendering module for rendering a further image of said series.
According to still another aspect of the present invention there is provided a method of processing image data for creating an image by rendering graphical objects to be composited according to a compositing expression, comprising the steps of:
dividing a space in which said objects are defined into a plurality of regions in accordance with outlines of the objects;
examining a part of the space by utilizing each said region; and
modifying the compositing expression based on a result of said examining step.